%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% a0poster Portrait Poster
% LaTeX Template
% Version 1.0 (22/06/13)
%
% The a0poster class was created by:
% Gerlinde Kettl and Matthias Weiser (tex@kettl.de)
% 
% This template has been downloaded from:
% http://www.LaTeXTemplates.com
%
% License:
% CC BY-NC-SA 3.0 (http://creativecommons.org/licenses/by-nc-sa/3.0/)
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%----------------------------------------------------------------------------------------
%	PACKAGES AND OTHER DOCUMENT CONFIGURATIONS
%----------------------------------------------------------------------------------------

\documentclass[a0,portrait]{a0poster}

\usepackage{adjustbox}
\usepackage{threeparttable}
\usepackage{multirow}
\usepackage{float}

\usepackage{multicol} % This is so we can have multiple columns of text side-by-side
\columnsep=100pt % This is the amount of white space between the columns in the poster
\columnseprule=3pt % This is the thickness of the black line between the columns in the poster

\usepackage{url}

\usepackage[svgnames]{xcolor} % Specify colors by their 'svgnames', for a full list of all colors available see here: http://www.latextemplates.com/svgnames-colors

\usepackage{times} % Use the times font
%\usepackage{palatino} % Uncomment to use the Palatino font

\usepackage{graphicx} % Required for including images
\graphicspath{{figures/}} % Location of the graphics files
\usepackage{booktabs} % Top and bottom rules for table
\usepackage[font=small,labelfont=bf]{caption} % Required for specifying captions to tables and figures
\usepackage{amsfonts, amsmath, amsthm, amssymb} % For math fonts, symbols and environments
\usepackage{wrapfig} % Allows wrapping text around tables and figures

\begin{document}

%----------------------------------------------------------------------------------------
%	POSTER HEADER 
%----------------------------------------------------------------------------------------

% The header is divided into two boxes:
% The first is 75% wide and houses the title, subtitle, names, university/organization and contact information
% The second is 25% wide and houses a logo for your university/organization or a photo of you
% The widths of these boxes can be easily edited to accommodate your content as you see fit

\begin{minipage}[b]{0.8\linewidth}
\veryHuge \color{NavyBlue} \textbf{EMS: History-Driven Mutation for\\ Coverage-based Fuzzing} \color{Black}\\ % Title
%\Huge\textit{An Exploration of Complexity}\\[2cm] % Subtitle
\huge \textbf{Chenyang Lyu, Shouling Ji, Xuhong Zhang, Hong Liang, Binbin Zhao,\\ Kangjie Lu, and Raheem Beyah}\\[0.5cm] % Author(s)
\huge Zhejiang University, Zhejiang University NGICS Platform,\\
Georgia Institute of Technology,\\
  University of Minnesota\\[0.4cm] % University/organization
\Large \texttt{(puppet, sji, zhangxuhong, hongliang)@zju.edu.cn,\\ binbin.zhao@gatech.edu, kjlu@umn.edu, rbeyah@ece.gatech.edu}\\
\end{minipage}
%
\begin{minipage}[b]{0.2\linewidth}
\includegraphics[width=15cm]{NDSS.png}\\
\end{minipage}

\vspace{1cm} % A bit of extra whitespace between the header and poster content

%----------------------------------------------------------------------------------------

\begin{multicols}{3} % This is how many columns your poster will be broken into, a portrait poster is generally split into 2 columns

%----------------------------------------------------------------------------------------
%	ABSTRACT
%----------------------------------------------------------------------------------------

\color{Navy} % Navy color for the abstract

\begin{abstract}

We first propose a lightweight and efficient Probabilistic Byte Orientation Model (PBOM) that properly captures the byte-level mutation strategies from intra- and inter-trial history and thus can effectively trigger unique paths and crashes. We then present a novel history-driven mutation framework named EMS that employs PBOM as one of the mutation operators to probabilistically provide desired mutation byte values according to the input ones.

\end{abstract}

%----------------------------------------------------------------------------------------
%	INTRODUCTION
%----------------------------------------------------------------------------------------

\color{SaddleBrown} % SaddleBrown color for the introduction

\section*{Introduction}

Fuzzing is the most effective automatic vulnerability detection technology at present.It detects possible vulnerabilities in the program by randomly producing a large number of abnormal inputs.Due to the uncertainty of random process, researchers have proposed a variety of methods to improve its detection efficiency.Among them, coverage-guided fuzzing is one of the most effective methods.This method collects coverage information during program operation, and uses it to guide the generation of test cases.Although researchers have proposed many methods to improve fuzzing based on coverage, we find that the existing methods lack fine-grained reuse of fuzzing history.We think that due to a large number of code reuse in programs, there is information hidden in the fuzzing history that can be used to enhance the performance of fuzzing.Using this information, fuzzers can find new paths faster, and have a higher probability to trigger vulnerabilities.To achieve this goal, we propose \textit{Probabilistic Byte Orientation Model (PBOM)} to learn and reuse fuzzing history, and implement this method in a generic framework named \textit{EMS}.We compare EMS with state-of-the-art coverage-based Fuzzers\cite{fioraldi2020afl++, lyu2019mopt, yue2020ecofuzz, yun2018qsym, afl.org}, and find that the ability of EMS to find new vulnerabilities is obviously better than other Fuzzers.

%----------------------------------------------------------------------------------------
%	OBJECTIVES
%----------------------------------------------------------------------------------------

\color{DarkSlateGray} % DarkSlateGray color for the rest of the content

\section*{Main Objectives}

\begin{enumerate}
\item We discover that both intra- and inter-trial fuzzing history contain rich knowledge of the key mutation strategies that lead to the discovery of unique paths and crashes.
\item We propose a lightweight and efficient PBOM to capture the mutation strategies that trigger unique paths and crashes in the intra- and inter-trial history.
\item We implement EMS based on the state-of-the-art fuzzer MOPT and construct the prototype of EMS. Then, we evaluate EMS against AFL, QSYM, MOPT, MOPT-dict, Ecofuzz, and AFL++ on 9 real world programs.
\item We report all of the discovered vulnerabilities to the vendors to improve the programs’ security. Also, we will open source EMS at https://github.com/puppet-meteor/EMS to facilitate the research in the fuzzing area.
\end{enumerate}

%----------------------------------------------------------------------------------------
%	MATERIALS AND METHODS
%----------------------------------------------------------------------------------------

\section*{Motivation}

We think that there are a lot of code reuse in same or different programs.For example, programs will use the same immediate operands in different comparison instructions, and different programs will also use the same immediate operands in comparison instructions.In addition, the same module will be reused in different programs which are from the same vendor.To prove our point, we compared the reuse of immediate operands related to comparison instructions in a program, and the results are shown in table \ref{Table1}.Among them, in order to enhance persuasion, we exclude some universal immediate operands.It can be seen that there are a lot of immediate operands reuse in the program.

\vspace{0.5cm}
\begin{table}[H]
\caption{Statistics of the number of immediate operands and their usages by the \textit{cmp} instruction.}\label{Table1}
\centering
\begin{threeparttable}
\begin{adjustbox}{width=\columnwidth,center}
  \begin{tabular}{c c c c c}
    \toprule
     & & \small{Singular\tnote{a}} & \small{Repetitive\tnote{b}} & \small{Total} \\
    \midrule
    \multirow{2}{*}{pdfimages} & Number of immediate operands & 15 & 21 & 36 \\
     & Number of usages of immediate operands &  15 & 46 & 61 \\
    \midrule
    \multirow{2}{*}{objdump} & Number of immediate operands & 25 & 34 & 29 \\
     & Number of usages of immediate operands &  25 &  195 & 220 \\
    \midrule
    \multirow{2}{*}{nasm} & Number of immediate operands & 6 & 5 & 11 \\
     & Number of usages of immediate operands &  6 &  35 & 41 \\
    \bottomrule
  \end{tabular}
\end{adjustbox}
  \begin{tablenotes}
    \footnotesize
    \item[a] If an immediate operand is used only once, it is singular.
    \item[b] If an immediate operand is used more than once, it is repetitive.
  \end{tablenotes}
\end{threeparttable}
\end{table}
\vspace{0.5cm}

After that, we compare the immediate operands used to compare instructions in different programs, and the results are shown in figure \ref{Figure1}.It can be seen that the number of the same immediate operands in different programs can't be neglected.

\vspace{0.5cm}
\begin{figure}[H]
\centering
\includegraphics[width = 0.8\linewidth]{figure1.png}
\caption{\textbf{The percentage of usages of the same immediate operands, i.e., the number of usages of the same immediate operands employed in both programs divided by the number of usages of all the immediate operands in each program.}}
\label{Figure1}
\end{figure}
\vspace{0.5cm}

Finally, we compare the number of shared blocks in different programs from a vendor.The results are shown in figure\ref{Figure2}.It can be seen that a considerable number of modules are reused in the program developed by the same vendor.

\vspace{0.5cm}
\begin{figure}[H]
\centering
\includegraphics[width = 0.8\linewidth]{figure2.png}
\caption{\textbf{The number of shared basic blocks and unique basic blocks triggered in three programs from the same vendor.}}
\label{Figure2}
\end{figure}
\vspace{0.5cm}

To sum up, we think that the information collected in one fuzzing can guide other fuzzing to find new vulnerabilities faster.
%----------------------------------------------------------------------------------------
%	Methods 
%----------------------------------------------------------------------------------------

\section*{Methods}

The complete EMS framework is shown in Figure \ref{Figure3}.The framework adds PBOMinitialization, PBOMoperator and PBOMupdate on the basis of MOPT\cite{lyu2019mopt}.Among them, PBOMinitialization will create an inter-PBOM structure using information from other fuzzing.PBOM structure will be used by fuzzer as a unique mutation operator in the mutation stage.PBOM update collects information in fuzzing and periodically updates the intra-PBOM structure with this information.

\vspace{0.5cm}
\begin{figure}[H]
\centering
\includegraphics[width = 0.8\linewidth]{figure3.png}
\caption{\textbf{The framework of EMS.}}
\label{Figure3}
\end{figure}
\vspace{0.5cm}

The PBOM structure is shown in Figure \ref{Figure4}, which uses a linked list to store the collected information.When a mutation finds a new path, the information related to the mutation will be recorded in the PBOM structure.The recorded information includes Input Byte Values, Len, Output Byte Values, Mutation, Frequency.When the PBOM operator is used for mutation, the Fuzzer will randomly select a certain length of byte and find relevant records in the PBOM structure according to the value of the byte.If the record exists, select the Mutation Node from the relevant records and use the information in it for mutation.The selection method is determined by the mutation stage.In the deterministic stage, select all the Mutation Node in the corresponding record, and in the havoc stage, randomly select one Mutation Node.

\vspace{0.5cm}
\begin{figure}[H]
\centering
\includegraphics[width = 0.8\linewidth]{figure4.png}
\caption{\textbf{The data structure of PBOM.}}
\label{Figure4}
\end{figure}
\vspace{0.5cm}

The EMS workflow is shown in figure\ref{Figure5}

\vspace{0.5cm}
\begin{figure}[H]
\centering
\includegraphics[width = 0.8\linewidth]{figure5.png}
\caption{\textbf{The workflow of EMS.}}
\label{Figure5}
\end{figure}
\vspace{0.5cm}

%----------------------------------------------------------------------------------------
%	Result
%----------------------------------------------------------------------------------------

\section*{Result}

We compare EMS with state of the art coverage based Fuzzers., and the results are shown in figure\ref{Table2}.The results show that EMS can find more vulnerablities than other with state-of-the-art coverage-based Fuzzers.

\vspace{0.5cm}
\begin{table}[H]
\caption{The number of unique vulnerabilities after deduplication in 16 trials.}
\label{Table2}
\centering
\begin{adjustbox}{width=\columnwidth,center}
  \begin{tabular}{c c c c c c c c}
    \toprule
     & AFL & QSYM & MO\small{PT} & MO\small{PT}-dict & Eco-Fuzz & AFL++ & EMS \\ 
    \midrule
    pdfimages & 2 & 3 & 4 & 5 & 7 & 13 & 15\\
    pdftotext & 2 & 6 & 9 & 9 & 9 & 6 & 13 \\
    objdump & 5 & 11 & 3 & 6 & 18 & 22 & 30 \\
    infotocap & 0 & 0 & 6 & 6 & 3 & 7 & 7 \\
    cflow & 1 & 4 & 6 & 7 & 6 & 7 & 9 \\
    nasm & 0 & 0 & 11 & 15 & 13 & 20 & 18 \\
    w3m & 0 & 1 & 0 & 1 & 0 & 0 & 11\\
    mujs & 4 & 3 & 4 & 6 & 6 & 6 & 7 \\
    mp3gain & 8 & 11 & 17 & 18 & 16 & 18 & 20 \\
    \midrule
    total & 22 & 39 & 60 & 73 & 78 & 99 & 130 \\
    \bottomrule
  \end{tabular}
\end{adjustbox}
\end{table}
\vspace{0.5cm}

%----------------------------------------------------------------------------------------
%	CONCLUSIONS
%----------------------------------------------------------------------------------------

\color{SaddleBrown} % SaddleBrown color for the conclusions to make them stand out

\section*{Conclusions}

\begin{itemize}
\item Most of the immediate operands employed by \textit{cmp} are repetitive in one program, and different programs have the same immediate operands, which are the majority of all the operands.
\item Different programs developed by the same vendor invoke the same codes and contain the shared basic blocks in their execution paths, introducing more kinds of the same path constraints.
\item EMS can serve as a new direction to improve the coverage and vulnerability discovery of mutation-based fuzzers.
\end{itemize}

%----------------------------------------------------------------------------------------
%	FORTHCOMING RESEARCH
%----------------------------------------------------------------------------------------

\color{DarkSlateGray} % Set the color back to DarkSlateGray for the rest of the content
\section*{Forthcoming Research}

Future work mainly focuses on three aspects:

\begin{enumerate}
\item Because different mutation operation efficiency is different, the mutation type should be considered when selecting the Mutation Node.
\item Since the location of the mutation byte will affect the mutation result, location should be considered when collenting the history information.
\item Using machine learning algorithm can achieve better results, but the overhead is too large and affects the execution speed.Even so, machine learning algorithms may have more potential because of their high fitting ability.
\end{enumerate}
 %----------------------------------------------------------------------------------------
%	REFERENCES
%----------------------------------------------------------------------------------------

\nocite{*} % Print all references regardless of whether they were cited in the poster or not
\tiny
\bibliographystyle{plain} % Plain referencing style
\bibliography{ref} % Use the example bibliography file sample.bib

%----------------------------------------------------------------------------------------

\end{multicols}
\end{document}